package com.example.interview.algorithm;

/**
 * 
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月27日 上午11:01:30
 * 题目一： 数组种重复的数字
 * 找出数字种重复的数字。 在一个长度为n的数组中所有的数字都在0到n-1的范围内（非法值校验）。数组中某些元素是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 找出数组中任意一个重复的数字。例如：如果长度为7的数组{3,1,2,4,2,5,3}，那么对应的输出结果是重复的数字2或者3.
 */
public class Test03_1Duplicate {

	public static boolean duplicate(int[] numbers) {
		if (numbers==null||numbers.length<=0) {
			return false;
		}
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i]<0||numbers[i]>numbers.length-1) {
				return false;
			}
		}
		// 3,1,2,4,2,5,3
		for(int i=0;i<numbers.length;i++) {
			while(numbers[i]!=i) {
				if (numbers[i]==numbers[numbers[i]]) {
					System.out.println(numbers[i]);
					return true;
				}
				int temp=numbers[i];
				numbers[i]=numbers[temp];
				numbers[temp]=temp;
				
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		int[] numbers=new int[] {3,1,2,4,2,5,3};
		duplicate(numbers);
	}
}
